package 前缀和;

import java.util.HashMap;
import java.util.Map;
/*给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。*/
// 以 i 位置为结尾的所有子数组，[0,i-1]区间内，有多少个前缀和等于 sum[i]-k
/*1.前缀和加入哈希表的时机：在计算i位置之前，哈希表里只保存[0,i-1]位置的前缀和
* 2.用一个变量sum来标记前一个位置的前缀和
* 3.如果整个前缀和等于 k 则令 hash（0，1）  无论 k 是多少，和为 0 的子数组都会被统计到，并且确保了算法的准确性。 */
/*https://leetcode.cn/problems/subarray-sum-equals-k/description/*/
public class 和为K的子数组 {

    public int subarraySum(int[] nums, int k) {

        Map<Integer,Integer> hash =  new HashMap<Integer,Integer>();
        hash.put(0,1);
        int sum=0,ret=0;
        for(int x:nums){
            sum+=x;// 计算出当前位置的前缀和
            ret+=hash.getOrDefault(sum-k,0);//统计结果
            hash.put(sum,hash.getOrDefault(sum,0)+1); // 把当前的前缀和丢到哈希表里
        }
        return ret;


    }
}

/*首先，让我们逐行解释这段代码的作用：

Map<Integer, Integer> hash = new HashMap<Integer, Integer>(); 创建一个哈希表，用于存储累积和及其对应的出现次数。

hash.put(0, 1); 将初始和为0的情况放入哈希表中，并设置出现次数为1。

int sum = 0, ret = 0; 初始化累积和 sum 为0，子数组个数 ret 为0。

for (int x : nums) 遍历数组 nums 中的每个元素。

sum += x; 将当前元素值累加到 sum 中，表示当前的累积和。

ret += hash.getOrDefault(sum - k, 0); 这行代码的目的是统计和为 k 的子数组个数。

sum - k 表示当前累积和减去目标值 k，得到一个特定的差值。

hash.getOrDefault(sum - k, 0) 尝试从哈希表中获取以 sum - k 为键的值，如果不存在，则返回默认值0。

这个操作的目的是查找之前的累积和中是否存在一个值，使得当前累积和减去该值等于目标值 k。如果存在，说明存在一个子数组的和为 k，将其出现次数累加到 ret 中。

hash.put(sum, hash.getOrDefault(sum, 0) + 1); 将当前累积和及其出现次数放入哈希表中。

hash.getOrDefault(sum, 0) 尝试从哈希表中获取当前累积和的出现次数，如果不存在，则返回默认值0。

hash.getOrDefault(sum, 0) + 1 表示当前累积和的出现次数加1。

这个操作的目的是更新哈希表中当前累积和的出现次数。

循环结束后，返回 ret，即和为 k 的子数组个数。

综上所述，ret+=hash.getOrDefault(sum-k,0); 的作用是统计和为 k 的子数组个数，hash.put(sum,hash.getOrDefault(sum,0)+1); 的作用是更新累积和及其出现次数的哈希表。这样通过遍历数组，累积和的计算和哈希表的更新，可以高效地求解和为 k 的子数组个数。*/
